#pragma once

#include <vector>
#include <utility>

namespace sorting
{
    /**
     * @brief       直接插入排序
     * @tparam  T   基本数据类型
     * @param   vec 基本数据类型的数组
     */
    template <typename T>
    void DirectInsertionSort(std::vector<T> &vec)
    {
        using std::size_t;

        const size_t len = vec.size();
        if (len <= 1)
        {
            return;
        }

        for (size_t i = 1; i < len; ++i)
        {
            // 先存储 vec[i]
            const T tmp = vec[i];
            size_t j = i;

            while (j > 0 && tmp < vec[j - 1])
            {
                vec[j] = vec[j - 1];
                --j;
            }
            vec[j] = tmp;
        }
    }
} // namespace sorting